﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace _326._3的幂
{
    public class Solution
    {
        /// <summary>
        /// https://leetcode.cn/problems/power-of-three/
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public bool IsPowerOfThree(int n)
        {
            if (n == 0) return false;
            if (n == 1) return true;
            while (n % 3 != 0)
            {
                n /= 3;
                if (n == 1) return true;
            }
            return false;
        }
        Dictionary<int, bool> dict = new Dictionary<int, bool>()
        {
            {1          ,true  },
            {3          ,true  },
            {9          ,true  },
            {27         ,true  },
            {81         ,true  },
            {243        ,true  },
            {729        ,true  },
            {2187       ,true  },
            {6561       ,true  },
            {19683      ,true  },
            {59049      ,true  },
            {177147     ,true  },
            {531441     ,true  },
            {1594323    ,true  },
            {4782969    ,true  },
            {14348907   ,true  },
            {43046721   ,true  },
            {129140163  ,true  },
            {387420489  ,true  },
            { 1162261467,true } ,
        };
        public bool IsPowerOfThree2(int n)
        {
            return dict.ContainsKey(n);
        }

        public bool IsPowerOfThree3(int n)
        {
            List<int> a = new List<int> {
            1           ,
            3           ,
            9           ,
            27          ,
            81          ,
            243         ,
            729         ,
            2187        ,
            6561        ,
            19683       ,
            59049       ,
            177147      ,
            531441      ,
            1594323     ,
            4782969     ,
            14348907    ,
            43046721    ,
            129140163   ,
            387420489   ,
            1162261467  ,
           };



            return a.Contains(n);
        }

        public bool IsPowerOfThree4(int n)
        {
            return n > 0 && 1162261467 % n == 0;
        }

        /// <summary>
        /// 412. Fizz Buzz  https://leetcode.cn/problems/fizz-buzz/
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<string> FizzBuzz(int n)
        {
            IList<string> s = new List<string>();

            for (int i = 1; i <= n; i++)
            {
                if (i % 3 == 0 && i % 5 == 0)
                {
                    s.Add("FizzBuzz");
                }
                else if (i % 3 == 0)
                {
                    s.Add("Fizz");
                }
                else if (i % 5 == 0)
                {
                    s.Add("Buzz");
                }
                else
                {
                    s.Add(i.ToString());
                }
            }
            return s;

        }

        /// <summary>
        /// 204. 计数质数 方法一：枚举 https://leetcode.cn/problems/count-primes/
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public bool IsPrimes(int x)
        {
            if (x <= 1) return false;

            //for (int i = 2; i * i <= x; i++)
            for (int i = 2; i <= Math.Sqrt(x); i++)
            {
                if (x % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

        public int CountPrimes(int n)
        {
            if (n <= 1) return 0;
            int num = 0;
            for (int i = 2; i < n; i++)
            {
                if (IsPrimes(i))
                {
                    num++;
                    //Console.WriteLine(i);
                }
            }
            return num;
        }
        /// <summary>
        /// 方法二：埃氏筛
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int CountPrimes2(int n)
        {
            if (n <= 1) return 0;
            int[] nums = new int[n];

            int num = 0;
            for (int i = 2; i < n; i++)
            {
                if (nums[i] == 0)
                {
                    num++;

                    if ((long)i * i < n)
                    {

                        for (int j = i * i; j < n; j += i)
                        {
                            nums[j] = 1;
                        }
                    }
                }
            }
            return num;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Solution S = new Solution();

            Console.WriteLine(S.CountPrimes2(0));
            Console.WriteLine(S.CountPrimes2(1));
            Console.WriteLine(S.CountPrimes2(10));
            Console.WriteLine(S.CountPrimes2(1500000));
            Console.WriteLine(S.CountPrimes2(5 * (int)Math.Pow(10, 6)));
            Console.WriteLine(S.CountPrimes(5 * (int)Math.Pow(10, 6)));

            //for(var i = 0; i <= 20; i++)
            //{
            //    Console.WriteLine((int)Math.Pow(3,i));
            //}
            IList<string> ss = new Solution().FizzBuzz(15);
            for (int i = 0; i < ss.Count; i++)
            {
                Console.WriteLine(ss[i]);

            }
            Console.WriteLine(new Solution().IsPowerOfThree(19684));
            Console.WriteLine(new Solution().IsPowerOfThree(1));
            Console.WriteLine(new Solution().IsPowerOfThree(27));
            Console.WriteLine(new Solution().IsPowerOfThree(0));
            Console.WriteLine(new Solution().IsPowerOfThree(9));
            Console.WriteLine(new Solution().IsPowerOfThree(45));

            Console.WriteLine();
            Console.WriteLine(new Solution().IsPowerOfThree2(19684));
            Console.WriteLine(new Solution().IsPowerOfThree2(1));
            Console.WriteLine(new Solution().IsPowerOfThree2(27));
            Console.WriteLine(new Solution().IsPowerOfThree2(0));
            Console.WriteLine(new Solution().IsPowerOfThree2(9));
            Console.WriteLine(new Solution().IsPowerOfThree2(45));

            Console.WriteLine();
            Console.WriteLine(new Solution().IsPowerOfThree3(19684));
            Console.WriteLine(new Solution().IsPowerOfThree3(1));
            Console.WriteLine(new Solution().IsPowerOfThree3(27));
            Console.WriteLine(new Solution().IsPowerOfThree3(0));
            Console.WriteLine(new Solution().IsPowerOfThree3(9));
            Console.WriteLine(new Solution().IsPowerOfThree3(45));


        }
    }
}
